package lc;
import java.util.*;
import org.junit.*;
public class Ex347 {
    class Solution1 {
        //f[i]记录次数为i的数是
        public int[] topKFrequent(int[] nums, int k) {
        
            int len = nums.length;
            Map<Integer, Node> map = new HashMap<>();
    
            for (int i = 0; i < len; i++) {
                if (map.containsKey(nums[i])) {
                    map.get(nums[i]).times++;
                } else {
                    map.put(nums[i], new Node(nums[i]));
                }
            }
    
            Queue<Node> queue = new PriorityQueue<>((n1, n2) -> n1.times - n2.times);
            for (int val: map.keySet()) {
                Node node = map.get(val);
                if (queue.size() < k) {
                    queue.offer(node);
                } else if (queue.peek().times < node.times) {
                    queue.poll();
                    queue.offer(node);
                }
            }
            return queue.stream().map(n1 -> n1.val).mapToInt(Integer::valueOf).toArray();
        }
    
        class Node {
            int val, times;
            public Node(int val) {
                this.val = val;
                this.times = 1;
            }
        }
        
    }


    class Solution {
        //先记录再排序
        public int[] topKFrequent(int[] nums, int k) {
        
            int len = nums.length;
            Map<Integer, Node> map = new HashMap<>();

            for (int i = 0; i < len; i++) {
                if (map.containsKey(nums[i])) {
                    map.get(nums[i]).times++;
                } else {
                    map.put(nums[i], new Node(nums[i]));
                }
            }
    
           //桶排序
            List<Integer>[] f = new List[len + 1];
           for (int n : map.keySet()) {
               Node node = map.get(n);
                if (f[node.times] == null) {
                    f[node.times] = new ArrayList<>();
                }
                f[node.times].add(node.val);
           }
           int[] res = new int[k];
           loop: for (int i = len; i >= 0; i--) {
               if (f[i] != null) {
                   for (int n: f[i]) {
                       res[--k] = n;
                       if (k == 0) break loop;
                   }
               }
           }
            return res;
        }
    
        class Node {
            int val, times;
            public Node(int val) {
                this.val = val;
                this.times = 1;
            }
        }
        
    }

    @Test
    public void test() {
        Solution s = new Solution();
        int[] nums = new int[]{1};
        System.out.println(Arrays.toString(s.topKFrequent(nums, 1)));
    }
}
